package previous.Test_0123;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Test {
    //二分查找
    public int search(int[] nums, int target) {
        int right=nums.length-1;
        int left=0;
        while(left<=right){
            //int mid=(left+right)/2;
            //为了避免溢出
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    //在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
           int left=0;
           int right=nums.length-1;
           int[] n=new int[2];
           n[0]=-1;
           n[1]=-1;
           if(nums.length==0){
               return n;
           }
           while(left<right){
               //找左端点
               int mid=left+(right-left)/2;
               if(nums[mid]>=target){
                   right=mid;
               }else if(nums[mid]<target){
                   left=mid+1;
               }
           }
           //判断是否有结果
           if(nums[left]==target){
               n[0]=left;
           }else{
               return n;
           }
         left=0;
         right=nums.length-1;
           while(left<right){
            //找右端点
            int mid=left+(right-left+1)/2;
            if(nums[mid]<=target){
                left=mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }
        }
            n[1]=right;
        return n;
    }
    //x的算术平方根
    //mid*mid<=x,left=mid;
       //      >x  right=mid-1
    public int mySqrt(int x) {
        //数据太大会溢出，所以为long类型
          long left=1;
          long right=x;
          if(x<1){
              return 0;
          }
            while(left<right){
                //右端点
                long mid=left+(right-left+1)/2;
                if(mid*mid<=x){
                    left=mid;
                }else{
                    right=mid-1;
                }
            }
        return (int)left;
    }
    //搜索插入位置
    public int searchInsert(int[] nums, int target) {
          int left=0,right=nums.length-1;
          while(left<right){
              int mid=left+(right-left)/2;
              if(nums[mid]>=target){
                  right=mid;
              }else{
                  left=mid+1;
              }
          }

         return left;
    }
}
